package Aleehot100;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: c09
 * Package: Aleehot100
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/22 20:49
 * @Version 1.0
 * @Since 1.0
 */
public class c09 {

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
    }


    /**
     * 找到字符串中所有字母异位词
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        char[] sarr = s.toCharArray();
        char[] parr = p.toCharArray();

        int n = sarr.length;
        int m = parr.length;
        ArrayList<Integer> res = new ArrayList<>();
        if(n < m) {
            return res;
        }

        // 差异数组 - 滑动窗口
        int[] count = new int[256];

        for (int i = 0; i < m; i++) {
            count[parr[i]] --;
            count[sarr[i]] ++;
        }

        int diff = 0;
        for (int i = 0; i < 256; i++) {
            if(count[i] != 0) {
                diff ++;
            }
        }


        if(diff == 0) {
            res.add(0);
        }

        for (int i = 0; i < n - m; i++) {
            // 减元素
            if (count[sarr[i]] == 1) {
                diff--;
            } else if (count[sarr[i]] == 0) {
                diff++;
            }
            count[sarr[i]]--;

            // 加元素
            if (count[sarr[i + m]] == 0) {
                diff++;
            } else if (count[sarr[i + m]] == -1) {
                diff--;
            }
            count[sarr[i + m]]++;
            if(diff == 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}
